Leetcode 236.二叉树的最近公共祖先

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中 最近公共祖先 的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

1
2
3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

1
2
3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 $[2, 10^5]$ 内。
• $-10^9 <= Node.val <= 10^9$
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

链接：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

题目分析

  这道题应该是使用递归的方法，按照深度优先搜索寻找两个结点的最近祖先。我们使用函数 bool dfs() 进行递归遍历，而函数的返回值是子树中是否含有 p 或者 q。为什么要这么做？题目中给出的条件中提到，p != q，并且最近祖先的定义中，祖先是包含本身的。那么 p 和 q 的最近祖先可能是 p 本身或者 q 本身或者某个结点满足 p 和 q 分别在它的两个子树中。那么我们的返回值就无需区分 p 和 q，只需要知道子树中是否包含这两个之一（因为我们是从上往下遍历，递归的时候是从下往上返回，找到的第一个祖先就是最近祖先）。
  只要 root 的左右子树都含有 p 或 q，或者 root 是 p 或 q 中的一个，并且左右子树中含有 p 或 q，则 root 就是答案了，我们可以使用一个全局变量直接进行记录。而函数的返回结果就是左右子树中含有 p 或 q 或者本身就是 p 或 q。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    TreeNode *ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr) return false;
        bool left = dfs(root->left, p, q);
        bool right = dfs(root->right, p, q);
        if((left && right) || ((left || right) && (root == p || root == q))){
            ans = root;
        }
        return left || right || root == p || root == q;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。我们对二叉树进行了一次深度优先遍历。
  空间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。取决于递归栈的深度，最坏情况下二叉树是一条链，栈深度达到了 $n$。